Functional dependencies
A functional dependency is a constraint that specifies the relationship between two sets of attributes where one set can accurately determine the value of other sets. It is denoted as X → Y, where X is a set of attributes that is capable of determining the value of Y. The attribute set on the left side of the arrow, X is called Determinant, while on the right side, Y is called the Dependent.
Example:
roll_no | name | dept_name | dept_building |
---|---|---|---|
42 | abc | CO | A4 |
43 | pqr | IT | A3 |
44 | xyz | CO | A4 |
45 | xyz | IT | A3 |
46 | mno | EC | B2 |
47 | jkl | ME | B2 |
From the above table we can conclude some valid functional dependencies:
- roll_no → { name, dept_name, dept_building },→ Here, roll_no can determine values of fields name, dept_name and dept_building, hence a valid Functional dependency
- roll_no → dept_name , Since, roll_no can determine whole set of {name, dept_name, dept_building}, it can determine its subset dept_name also.
- dept_name → dept_building , Dept_name can identify the dept_building accurately, since departments with different dept_name will also have a different dept_building
- More valid functional dependencies: roll_no → name, {roll_no, name} ⇢ {dept_name, dept_building}, etc.
Here are some invalid functional dependencies:
- name → dept_name Students with the same name can have different dept_name, hence this is not a valid functional dependency.
- dept_building → dept_name There can be multiple departments in the same building, For example, in the above table departments ME and EC are in the same building B2, hence dept_building → dept_name is an invalid functional dependency.
- More invalid functional dependencies: name → roll_no, {name, dept_name} → roll_no, dept_building → roll_no, etc.
Armstrong’s axioms/properties of functional dependencies:
- Reflexivity: If Y is a subset of X, then X→Y holds by reflexivity rule
For example, {roll_no, name} → name is valid. - Augmentation: If X → Y is a valid dependency, then XZ → YZ is also valid by the augmentation rule.
For example, If {roll_no, name} → dept_building is valid, hence {roll_no, name, dept_name} → {dept_building, dept_name} is also valid.→ - Transitivity: If X → Y and Y → Z are both valid dependencies, then X→Z is also valid by the Transitivity rule.
For example, roll_no → dept_name & dept_name → dept_building, then roll_no → dept_building is also valid.
Types of Functional dependencies in DBMS:
- Trivial functional dependency
- Non-Trivial functional dependency
- Multivalued functional dependency
- Transitive functional dependency
1. Trivial Functional Dependency
In Trivial Functional Dependency, a dependent is always a subset of the determinant.
i.e. If X → Y and Y is the subset of X, then it is called trivial functional dependency
For example,
roll_no | name | age |
---|---|---|
42 | abc | 17 |
43 | pqr | 18 |
44 | xyz | 18 |
Here, {roll_no, name} → name is a trivial functional dependency, since the dependent name is a subset of determinant set {roll_no, name}
Similarly, roll_no → roll_no is also an example of trivial functional dependency.
2. Non-trivial Functional Dependency
In Non-trivial functional dependency, the dependent is strictly not a subset of the determinant.
i.e. If X → Y and Y is not a subset of X, then it is called Non-trivial functional dependency.
For example,
roll_no | name | age |
---|---|---|
42 | abc | 17 |
43 | pqr | 18 |
44 | xyz | 18 |
Here, roll_no → name is a non-trivial functional dependency, since the dependent name is not a subset of determinant roll_no
Similarly, {roll_no, name} → age is also a non-trivial functional dependency, since age is not a subset of {roll_no, name}
3. Multivalued Functional Dependency
In Multivalued functional dependency, entities of the dependent set are not dependent on each other.
i.e. If a → {b, c} and there exists no functional dependency between b and c, then it is called a multivalued functional dependency.
For example,
roll_no | name | age |
---|---|---|
42 | abc | 17 |
43 | pqr | 18 |
44 | xyz | 18 |
45 | abc | 19 |
Here, roll_no → {name, age} is a multivalued functional dependency, since the dependents name & age are not dependent on each other(i.e. name → age or age → name doesn’t exist !)
4. Transitive Functional Dependency
In transitive functional dependency, dependent is indirectly dependent on determinant.
i.e. If a → b & b → c, then according to axiom of transitivity, a → c. This is a transitive functional dependency
For example,
enrol_no | name | dept | building_no |
---|---|---|---|
42 | abc | CO | 4 |
43 | pqr | EC | 2 |
44 | xyz | IT | 1 |
45 | abc | EC | 2 |
Here, enrol_no → dept and dept → building_no,
Hence, according to the axiom of transitivity, enrol_no → building_no is a valid functional dependency. This is an indirect functional dependency, hence called Transitive functional dependency.